import { cloneDeep } from 'lodash-es'

declare type ObjectRecord = Record<any, any>

// 参数校验
function commonParamsValid(children: string) {
  if (children === '') {
    throw new Error('children is not a valid string')
  }
}

/**
 * 遍历 tree
 * @param {object[]} tree
 * @param {function} cb - 回调函数
 * @param {string} children - 子节点 字段名
 * @param {string} mode - 遍历模式，DFS：深度优先遍历 BFS：广度优先遍历
 * @return {void} Do not return anything
 */
export function treeForEach<T extends ObjectRecord>(
  tree: T[],
  cb: (item: T, parent: T | null) => void,
  children = 'children',
  mode: 'DFS' | 'BFS' = 'DFS'
): void {
  commonParamsValid(children)

  // 深度优先遍历 depth first search
  function DFS(treeData: T[], parent: T | null) {
    for (const item of treeData) {
      cb(item, parent)

      if (Array.isArray(item[children])) {
        DFS(item[children], item)
      }
    }
  }

  // 广度优先遍历 breadth first search
  function BFS(treeData: T[]) {
    interface QueenItem {
      node: T,
      parent: T | null
    }

    const queenFormat = (data: T[], parent: T | null): QueenItem[] => data.map(node => ({ node, parent }))

    const queen = queenFormat(treeData, null)

    while (queen.length > 0) {
      const { node, parent } = queen.shift() as QueenItem

      cb(node, parent)

      if (Array.isArray(node[children])) {
        queen.push(...queenFormat(node[children], node))
      }
    }
  }

  if (mode === 'BFS') {
    BFS(tree)
  } else {
    DFS(tree, null)
  }
}

/**
 * 查询 tree item
 * 根据属性值查询指定选项，仅返回首次查询到的选项
 * @param {object[]} tree
 * @param {function} cb - 回调函数
 * @param {string} children - 子节点 字段名
 * @param {string} mode - 遍历模式，DFS：深度优先遍历 BFS：广度优先遍历
 * @return {void} treeItem
 */
export function treeFindItem<T extends ObjectRecord>(
  tree: T[],
  cb: (item: T) => boolean,
  children = 'children',
  mode: 'DFS' | 'BFS' = 'DFS'
): T | null {
  commonParamsValid(children)

  // 深度优先遍历 depth first search
  function DFS(treeData: T[]) {
    // eslint-disable-next-line
    for (const item of treeData) {
      const res = cb(item)

      if (res) {
        return item
      }

      if (Array.isArray(item[children])) {
        DFS(item[children])
      }
    }

    return null
  }

  // 广度优先遍历 breadth first search
  function BFS(treeData: T[]) {
    const queen = treeData

    while (queen.length > 0) {
      const item = queen.shift() as T

      const res = cb(item)

      if (res) {
        return item
      }

      if (Array.isArray(item[children])) {
        queen.push(...item[children])
      }
    }

    return null
  }

  return mode === 'BFS' ? BFS(tree) : DFS(tree)
}

/**
 * tree 转 数组
 * @param {object[]} tree
 * @param {string} children - 子节点 字段名
 * @param {string} mode - 遍历模式，DFS：深度优先遍历 BFS：广度优先遍历
 * @return {array} treeItem[]
 */
export function treeToList<T extends ObjectRecord>(
  tree: T[],
  children = 'children',
  mode: 'DFS' | 'BFS' = 'DFS'
): T[] {
  commonParamsValid(children)

  tree = cloneDeep(tree)

  const list: T[] = []

  treeForEach(tree, (item : T) => {
    list.push(item)
  }, children, mode)

  list.forEach((item: T) => {
    delete item[children] // 会改变 原数据
  })

  return list
}

/**
 * 数组 转 tree
 * @param {object[]} list
 * @param {object} options
 * @param {string|number|null|undefined} options.rootID - 根节点ID
 * @param {string|number} options.id - 唯一标识 字段名
 * @param {string|number} options.pid - 父节点ID 字段名
 * @param {string} options.children - 子节点 字段名
 * @return {array}
 */
export interface ListToTreeOptions {
  rootID?: number | string | null
  id?: string
  pid?: string
  children?: string
}
export function listToTree<T extends ObjectRecord>(
  list: T[],
  options: ListToTreeOptions
): T[] {
  const {
    rootID = null, // 根节点ID，pid === rootID 即为 一级节点
    id = 'id', // 唯一标识
    pid = 'pid', // 父节点ID 字段
    children = 'children' // 子节点 字段
  } = options || {}

  commonParamsValid(children)

  list = cloneDeep(list)

  const tree: T[] = []
  const map = list.reduce((res, item) => {
    res.set(item[id], item)

    return res
  }, new Map())

  Array.from(map.keys()).forEach(key => {
    const node = map.get(key)

    if (node[pid] === rootID) { // 一级节点，直接添加到 tree
      tree.push(node)
    } else { // 非一级节点，查找父级，并添加到父级 children 中
      const pNode = map.get(node[pid])

      // 如果 父级 不存在 则 不处理
      if (!pNode) {
        console.warn('parent node does not exist', node)

        return
      }

      if (Array.isArray(pNode[children])) {
        pNode[children].push(node)
      } else {
        pNode[children] = [node]
      }
    }
  })

  return tree
}